{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Power of Four"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPowerOfFour"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #4的幂"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>整数 <code>n</code> 是 4 的幂次方需满足：存在整数 <code>x</code> 使得 <code>n == 4<sup>x</sup></code></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 16\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= n &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能不使用循环或者递归来完成本题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [power-of-four](https://leetcode.cn/problems/power-of-four/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [power-of-four](https://leetcode.cn/problems/power-of-four/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['16', '5', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        if num <= 0:\n",
    "            return False\n",
    "        \n",
    "        # use loop\n",
    "        # while num % 4 == 0:\n",
    "        #     num /= 4\n",
    "        # return num == 1\n",
    "        \n",
    "        # # without loop\n",
    "        # return (math.log10(num)/math.log10(4)) % 1 == 0\n",
    "        \n",
    "        # other solutions\n",
    "        # return num > 0 and num & (num - 1) == 0 and num % 3 == 1\n",
    "        return num > 0 and math.log2(num) % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: 'int') -> 'bool':\n",
    "        return num!=0 and num & (num - 1) == 0 and num & 0b1010101010101010101010101010101 == num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: 'int') -> 'bool':\n",
    "        def f(num):\n",
    "            if num<=0:\n",
    "                return False\n",
    "            if num==1:\n",
    "                return True\n",
    "            if num%4!=0:\n",
    "                return False\n",
    "\n",
    "            a=num//4\n",
    "            return f(a)\n",
    "        return f(num)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isPowerOfFour(self, num):\n",
    "#         \"\"\"\n",
    "#         :type num: int\n",
    "#         :rtype: bool\n",
    "#         \"\"\"\n",
    "#         if num <= 0: return False\n",
    "#         while num % 4 == 0:\n",
    "#             num //= 4\n",
    "#         return num == 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num):\n",
    "        if num <= 0: return False\n",
    "        d = collections.Counter(bin(num))\n",
    "        return d['1'] == 1 and d['0'] % 2 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        if (num <= 0):\n",
    "            return False\n",
    "        else :\n",
    "            if num&(num-1) == 0:\n",
    "                if num & 0x55555555:                                \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return num > 0 and num & (num-1) == 0 and num & 1431655765 == num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if num == 1:\n",
    "            return True\n",
    "        if num == 4:\n",
    "            return True\n",
    "        if num < 4:\n",
    "            return False\n",
    "        if num > 4:\n",
    "            num = num / 4\n",
    "            return Solution.isPowerOfFour(self, num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if num <= 0:\n",
    "            return False\n",
    "        elif num == 1:\n",
    "            return True\n",
    "        else:\n",
    "            if num % 4 == 0:\n",
    "                return self.isPowerOfFour(num/4)\n",
    "            else: \n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        while num>=1:\n",
    "            if num == 1:\n",
    "                return(True)\n",
    "            num=num/4\n",
    "            print(num)\n",
    "        return(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        return num > 0 and num & (num-1) == 0 and num % 3 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        if num < 1:\n",
    "            return False\n",
    "        while num % 4 == 0:\n",
    "            num /= 4\n",
    "        \n",
    "        return num == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        if num == 1:\n",
    "            return True\n",
    "        elif num < 4:\n",
    "            return False\n",
    "        else:\n",
    "            if not num & (num-1) == 0:\n",
    "                return False\n",
    "            else:\n",
    "                return num & 0x55555555 == num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        n = num\n",
    "        if n == 0:\n",
    "            return False\n",
    "        while n%4 == 0:\n",
    "            n /=4\n",
    "        return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        if num<=0:\n",
    "            return False\n",
    "        if num==1:\n",
    "            return True\n",
    "        num=abs(num)\n",
    "        while num % 4==0:\n",
    "            num /= 4\n",
    "            if num==1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        while n > 1:\n",
    "            n /= 4;\n",
    "        # print(n);\n",
    "        if n == 1:\n",
    "            return True;\n",
    "        return False;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        return n>0 and n &(n-1) == 0 and n%3 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        while(n>=4):\n",
    "            if n%4==0:\n",
    "                n/=4\n",
    "            else:\n",
    "                return False\n",
    "        if n==1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isPowerOfFour(self, num: int) -> bool:\r\n",
    "        # import math\r\n",
    "\r\n",
    "        # return math.log10(num) / math.log10(4) % 1 == 0\r\n",
    "\r\n",
    "        return num > 0 and (num & (num - 1) == 0) and num % 3 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/problems/power-of-four/\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key, reduce\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter, deque\n",
    "from queue import Queue\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "\n",
    "def refreshGlobals():\n",
    "  pass\n",
    "\n",
    "\n",
    "refreshGlobals()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def isPowerOfFour(self, num):  # -> bool\n",
    "    if num & (num - 1):\n",
    "      return False\n",
    "    return bool(num.bit_length() % 2)\n",
    "\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().isPowerOfFour(*args), end='\\n-----\\n')\n",
    "\n",
    "\n",
    "  test(16)\n",
    "  test(5)\n",
    "  test(64)\n",
    "  test(0)\n",
    "  test(1)\n",
    "else:\n",
    "  print = lambda *args, **kwargs: None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        if n == 0:\n",
    "            return False\n",
    "        while True:\n",
    "            if n == 1:\n",
    "                return True\n",
    "            if n % 4 == 0:\n",
    "                n /= 4\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        if n<=0:\n",
    "            return False\n",
    "        else:\n",
    "            x=math.log(n,4)\n",
    "            if x%1==0:\n",
    "                return True \n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        if not n: return False\n",
    "        while n % 4 == 0:\n",
    "            n = n // 4\n",
    "        return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPowerOfFour(self, n: int) -> bool:\r\n",
    "        return n > 0 and (n & (n - 1)) == 0 and (n & 0xaaaaaaaa) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        if n==0:\n",
    "            return False\n",
    "        while n!=1:\n",
    "            if n%4 !=0:\n",
    "                return False\n",
    "            n=n//4\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        if n/4 == 0:\n",
    "            return False\n",
    "        elif n == 1:\n",
    "            return True\n",
    "\n",
    "        return self.isPowerOfFour(n/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        if n <= 0:\n",
    "            return False\n",
    "        while n % 4 == 0:\n",
    "            n /= 4\n",
    "        return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "\n",
    "        while n >= 4 :\n",
    "            if n % 4 != 0:\n",
    "                return False\n",
    "\n",
    "            n = n / 4\n",
    "\n",
    "        return int(n) == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, n: int) -> bool:\n",
    "        return n > 0 and n & (n - 1) == 0 and n & int('10101010101010101010101010101010', 2) == 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
